#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node *_left, Node *_right, Node *_next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
struct noode
{
    Node *node;
    int depth;
    noode(Node *node = nullptr, int depth = 0) : node(node), depth(depth){};
};
class Solution
{
public:
    queue<noode> que;
    Node *connect(Node *root)
    {
        noode nd1(root, 0), nd2;
        que.emplace(root, 0);
        while (que.empty() == false)
        {
            nd2 = que.front();
            que.pop();
            if (nd2.node == nullptr)
                continue;
            if (nd1.depth == nd2.depth)
            {
                nd1.node->next = nd2.node;
            }
            else if (nd1.depth < nd2.depth)
            {
                nd1.node->next = nullptr;
            }
            nd1 = nd2;
            que.emplace(nd2.node->left, nd2.depth + 1);
            que.emplace(nd2.node->right, nd2.depth + 1);
        }
        if (root != nullptr)
            root->next = nullptr;
        return root;
    }
};